An undeniable signature is a cryptographic scheme similar to a classical digital signature except that the recipient of a message cannot verify its validity using only the public key of the signer: he needs also to interact with this one in order to be convinced of validity of the signature. This opposes to the so called universal verifiability of classical digital signatures where anybody knowing the signer's public key is able to verify the signature at any time. In some applications such as signing a contract it is desirable to keep the signer's privacy by limiting the ability to verify this signature. However, an undeniable signature does not abandon the non repudiation property. Indeed, in the case of a dispute the signer could be compelled by an authority to prove the invalidity of a signature, otherwise this would be considered as an attempt of denying a valid signature. As a side benefit, undeniable signature could in principle be arbitrarily small e.g. as small as a MAC, although no such signatures were proposed so far. An undeniable signature scheme is composed of a signature generation algorithm, a confirmation protocol to prove the validity of a signature and a denial protocol in order to prove the invalidity of an alleged non signature. These two protocols often consist of an interactive proof.
Since the invention of the first undeniable signature scheme proposed by D. Chaum [see EP 0 318 097], a certain amount of work has been dedicated to its development and different improvements. Until the proposition of an undeniable signature scheme based on RSA by Gennaro et al. [U.S. Pat. No. 6,292,897], all the other undeniable signatures were based on the discrete logarithm problem. More recently, two undeniable signatures based on different problems have been proposed. The first one is based on pairings [B. Libert & J-J Quisquater “Identity based undeniable signatures” Cryptology ePrint Archive, Report 2003/206, 2003] and the second one is based on a quadratic field [see EP 1 185 025].